package tree

// https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xv7pir/
// 返回树的中序遍历
// 算法: 递归
func inorderTraversal(root *TreeNode) []int {
	if nil == root {
		return []int{}
	}
	retArr := make([]int, 0)
	retArr = recurForInorder(root, retArr)
	return retArr
}

func recurForInorder(root *TreeNode, orderArr []int) []int {
	if nil != root.Left {
		orderArr = recurForInorder(root.Left, orderArr)
	}
	orderArr = append(orderArr, root.Val)
	if nil != root.Right {
		orderArr = recurForInorder(root.Right, orderArr)
	}
	return orderArr
}

// 树结构定义，不需要提交
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
